In digital data communication systems, a sequence of bits (i.e. a signal representing binary digits) originates from a transmitter and is transmitted through a communications channel to a receiver. (Usually, data bits are grouped into "packets" consisting of a predetermined number of bits. The number commonly chosen, and selected herein, is eight bits, known as a byte.) If the communications channel were perfect, the sequence of bits received at the receiver would be identical to the transmitted data bits. However, communications channels are not perfect and, because of the presence of (electromagnetic) noise and other spurious signals, some of the received data bits may very well not be the same as the transmitted data bits. Accordingly, encoding and decoding devices have been designed to permit the detection and correction of errors occurring in a sequence of received data bits. Such systems determine if some of the bits of the received data bits differ from the transmitted data bits, and thereafter correct the error or errors, as the system permits.
A ("horizontal") data block coding system and apparatus is provided by the present invention and disclosed herein, to permit the detection and correction of one or more data bit errors occurring in any one data byte of a block of data bytes (or, more generally, data packets) or, in any two data bytes of a block of data bytes (again, or, more generally, data packets) providing that the two bytes have incorrect parity and can therefore be identified. Also provided by the present invention, and disclosed herein, is a ("horizontal and vertical") data block bundle coding system and apparatus. A bundle of data blocks, comprising an array of bytes, is formed by "stacking" data blocks one under another. Bundle coding permits the detection and correction of one or more data bit errors occurring in any one data byte or, in any two data bytes (or, more generally, data packets) providing that the two bytes can be identified, of a horizontal or vertical data block of the bundle. The bundle coding system of the present invention permits the full reconstruction of a missing data block of the bundle.
Bit errors occurring in a block of received digital data, in a data communication system, such as the videotex information system, known in Canada as Telidon* (*an official mark of the Government of Canada, Ministry of Communications, for which notice has been given under Section 9(l)(n)(iii) of the Canadian Trade Marks Act) often results in noticeable and unacceptable picture distortion which, in turn, necessitates requesting, at the receiver, retransmission of that data block and waiting for some time interval before the retransmitted data block has received. Both picture distortion and retransmission delays are undesirable and may contribute to user/subscriber dissatisfaction with the data system. Consequently, it is desirable to be able to detect bit errors occurring in a block, or bundle of blocks, of received data packets and to correct the errors at the receiver. Such error correction capability allows the correction of bit errors occurring in a block of data before the errors result in picture distortion and eliminates having to wait for the reception of a retransmitted data block.
Several error correction methods are known, and many different apparatus have been developed for encoding and decoding data blocks to permit the correction of bit errors. For example, there exists a single bit error correction method, denoted the SAB code, which is described in A Class of High Rate Codes for Byte-Oriented Information Systems, I.E.E.E. Transactions on Communications, Vol. COM-31, No. 3, March 1983.
Another example of a coding method which enables the correction of a single bit error occurring in a block of data bytes (or, more generally, data packets) is denoted herein as the "Product Code". This coding method parity encodes a block of data bits horizontally and vertically, adding one byte of redundancy (i.e. non-data byte) to the bits. One parity bit is added to each group of bits to form data bytes of fixed parity (i.e. for horizontal parity encoding), and one parity check byte (i.e. the redundant byte) is added to each block of data bytes (i.e. for vertical parity encoding). The parity check byte or, code byte, is defined such that the sum of all data bytes, and the code byte, equals 00000000 if even parity is selected, or 11111111 if odd parity is selected. Each bit of the code byte sets the parity of the bits of the data bytes arranged vertically in the block of "stacked" data bytes. This coding method is incorporated into the coding method used in the present invention and is discussed further below.
Another example of a coding method which permits the correction of a single bit error in a block of data bits, is denoted herein as the "Carleton Code". The Carleton Code redundant byte is determined algebraically from the data bytes of the data block to be encoded, in a manner similar to the coding method (Code C) used in the present invention. Details of the Carleton Code are described in pending U.S. application Ser. No. 596,397, now U.S. Pat. No. 4,599,722 issued 7/8/86, which is for another invention of the present inventor.
The above examples of coding methods involve one byte of redundancy per block of data bytes and each enables the correction of a single bit error (being either a data or parity bit). The coding method used in the present invention involves two bytes of redundancy per block of data bytes and, preferably, one or two blocks of code bytes of redundancy for bundle coding and enables the correction of up to two incorrect data bytes for each data block. Bundle coding can provide an even greater level of data correction by repetitively decoding a bundle of data blocks. This is because error corrections made during horizontal decoding may enable additional error corrections to be made upon vertical decoding, and vice-versa. That is, horizontal and vertical decoding can be repeated, in cycles, until the desired correction level is attained (for example, until no further corrections are made possible by the current decoding cycle).